home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_300 / 311_01 / db_idx.c < prev    next >
C/C++ Source or Header  |  1990-04-21  |  31KB  |  1,004 lines
  1. /****************************************************************************/
  2. /*                                                                          */
  3. /*                                                                          */
  4. /*      db_idx.c  v1.3  (c) 1987-1990  Ken Harris                           */
  5. /*                                                                          */
  6. /*                                                                          */
  7. /****************************************************************************/
  8. /*                                                                          */
  9. /*      This software is made available on an AS-IS basis. Unrestricted     */
  10. /*      use is granted provided that the copyright notice remains intact.   */
  11. /*      The author makes no warranties expressed or implied.                */
  12. /*                                                                          */
  13. /****************************************************************************/
  14.  
  15. #include "dblib.h"
  16.  
  17.  
  18. /*
  19.  *      db_add_idx  -  Add record to an index file
  20.  */
  21.  
  22. void db_add_idx(df, user_data)
  23.  DATA_FILE df;
  24.  char *user_data;
  25. {
  26.         FILE_HDR    fh;
  27.         INDEX_HDR ihdr;
  28.         INDEX_REC irec;
  29.         BUFFER     buf;
  30.         char     *rbuf, *src, *dst;
  31.         ushort     rec;
  32.         int        cnt;
  33.  
  34.         db_error     = 0;
  35.  
  36.         fh   = (FILE_HDR) df->df_fhdr->buf_data;
  37.         buf  = df->df_buf;
  38.         ihdr = (INDEX_HDR) buf->buf_data;
  39.         rbuf = buf->buf_data + sizeof(struct db_index_hdr);
  40.  
  41.         if (!fh->fh_root_ptr)
  42.         {       db_get_next_avail(df, buf);
  43.                 if (db_error) return;
  44.         }
  45.         else
  46.         {       db_find_insert_idx(df, user_data, fh->fh_key_size);
  47.                 if (db_match_blk)
  48.                         if (!(fh->fh_file_stat & DB_DUP_ALLOWED))
  49.                         {       db_error = DB_DUP_NOT_ALLOWED;
  50.                                 return;
  51.                         }
  52.         }
  53.                  
  54.         ihdr->idx_rec_cnt++;
  55.         rec = buf->buf_rec_inx;
  56.  
  57.         db_add_blk = buf->buf_cur_blk;
  58.         db_add_rec = buf->buf_rec_inx;
  59.  
  60.         if (rec <= ihdr->idx_rec_cnt)
  61.         {       src = rbuf + (rec - 1) * fh->fh_rec_size;
  62.                 dst = src + fh->fh_rec_size;
  63.                 cnt = (ihdr->idx_rec_cnt - rec + 1) * fh->fh_rec_size;
  64.                 memcpy(dst, src, cnt);
  65.         }                             
  66.         
  67.         irec = (INDEX_REC) src;
  68.         irec->idx_idx_ptr = 0;
  69.         dst = (char *) irec + fh->fh_ctl_size;
  70.         memcpy(dst, user_data, fh->fh_data_size);
  71.  
  72.         fh->fh_rec_cnt++;
  73.  
  74.         db_split_blk_idx(df);
  75.         if (db_error) return;
  76.  
  77.         db_put_blk(df, df->df_fhdr);
  78. }
  79.       
  80. /*
  81.  *      db_find_insert_idx  -  Find Insert Point in an index File
  82.  */
  83.  
  84. void db_find_insert_idx(df, key, key_size)
  85.  DATA_FILE df;
  86.  char *key;                         
  87.  int   key_size;
  88. {
  89.         FILE_HDR    fh;
  90.         INDEX_HDR ihdr;
  91.         INDEX_REC irec;
  92.         BUFFER     buf;
  93.         char     *rbuf, *ikey;
  94.         ulong      blk;
  95.         ushort     rec;
  96.         int          x;
  97.                        
  98.  
  99.         db_error     = 0;
  100.         db_match_blk = 0;
  101.         db_match_rec = 0;
  102.  
  103.         fh   = (FILE_HDR) df->df_fhdr->buf_data;
  104.         buf  = df->df_buf;
  105.         ihdr = (INDEX_HDR) buf->buf_data;
  106.         blk  = fh->fh_root_ptr;
  107.  
  108.         if (!key_size) key_size = fh->fh_key_size;
  109.  
  110.         while (blk)
  111.         {       db_get_blk(df, blk, buf);
  112.                 if (db_error) return;
  113.  
  114.                 rbuf = buf->buf_data + sizeof(struct db_index_hdr);
  115.  
  116.                 for (rec=1; rec <= ihdr->idx_rec_cnt; rec++)
  117.                 {       irec = (INDEX_REC) rbuf;
  118.                         ikey = rbuf + fh->fh_ctl_size;
  119.  
  120.                         x = memcmp(key, ikey, key_size);
  121.         
  122.                         if (x == 0)
  123.                         {       db_match_blk = blk;
  124.                                 db_match_rec = rec;
  125.                                 blk = irec->idx_idx_ptr;
  126.                                 break;
  127.                         }
  128.  
  129.                         if (x < 0)
  130.                         {       blk = irec->idx_idx_ptr;
  131.                                 break;
  132.                         }
  133.  
  134.                         rbuf += fh->fh_rec_size;
  135.  
  136.                         if (rec == ihdr->idx_rec_cnt)
  137.                         {       irec = (INDEX_REC) rbuf;
  138.                                 blk  = irec->idx_idx_ptr;
  139.                         }
  140.                 }        
  141.         }
  142.         buf->buf_rec_inx = rec;
  143. }
  144.  
  145. /*
  146.  *      db_split_blk_idx  -  Check for a block split
  147.  */
  148.  
  149. void db_split_blk_idx(df)
  150.  DATA_FILE df;
  151. {
  152.         FILE_HDR   fh;
  153.         BUFFER     buf,  tmp,  aux;
  154.         INDEX_HDR ihdr,  thdr, ahdr;
  155.         INDEX_REC  idx;
  156.         char     *hold, *rbuf, *src,  *dst;
  157.         ushort     cnt,  cnt1,  cnt2;
  158.         ushort     rec,  left, right;
  159.  
  160.         db_error = 0;
  161.  
  162.         fh  = (FILE_HDR) df->df_fhdr->buf_data;
  163.         buf = df->df_buf;
  164.         tmp = df->df_tmp;
  165.  
  166.         ihdr = (INDEX_HDR) buf->buf_data;
  167.  
  168.         if (ihdr->idx_rec_cnt <= fh->fh_recs_per_blk)
  169.         {       db_put_blk(df, buf);
  170.                 return;
  171.         }
  172.  
  173.         buf        = df->df_tmp;
  174.         tmp        = df->df_buf;
  175.         df->df_buf = buf;
  176.         df->df_tmp = tmp;
  177.         aux        = df->df_aux;
  178.  
  179.         db_get_next_avail(df, buf);
  180.         if (db_error) return;
  181.  
  182.         ihdr = (INDEX_HDR) buf->buf_data;
  183.         thdr = (INDEX_HDR) tmp->buf_data;
  184.         ahdr = (INDEX_HDR) aux->buf_data;
  185.  
  186.         left   = tmp->buf_cur_blk;
  187.         right  = buf->buf_cur_blk;
  188.  
  189.         cnt1 = thdr->idx_rec_cnt / 2;
  190.         cnt2 = thdr->idx_rec_cnt - (cnt1 + 1);
  191.  
  192.         ihdr->idx_parent  = thdr->idx_parent;
  193.         ihdr->idx_rec_cnt = cnt2;         
  194.  
  195.         src = tmp->buf_data + sizeof(struct db_index_hdr)
  196.                                                 + (cnt1 + 1) * fh->fh_rec_size;
  197.         dst = buf->buf_data + sizeof(struct db_index_hdr);
  198.         cnt = (cnt2 + 1) * fh->fh_rec_size;
  199.         memcpy(dst, src, cnt);
  200.  
  201.         db_put_blk(df, buf);
  202.         if (db_error) return;
  203.  
  204.         if (db_add_blk == tmp->buf_cur_blk)
  205.                 if (db_add_rec > cnt1 + 1)
  206.                 {       db_add_blk  =  buf->buf_cur_blk;
  207.                         db_add_rec -= cnt1 + 1;         
  208.                 }
  209.  
  210.         rbuf = buf->buf_data + sizeof(struct db_index_hdr);
  211.         if (!thdr->idx_parent)
  212.         {       if (tmp->buf_cur_blk != fh->fh_root_ptr)
  213.                 {       db_error = DB_INVALID_INDEX;
  214.                         return;
  215.                 }
  216.                 db_get_next_avail(df, buf);
  217.                 thdr->idx_parent = buf->buf_cur_blk;
  218.                 fh->fh_root_ptr  = buf->buf_cur_blk;
  219.                 idx              = (INDEX_REC) rbuf;
  220.                 rec              = 1;
  221.         }
  222.         else
  223.         {       db_get_blk(df, (long)thdr->idx_parent, buf);
  224.                 if (db_error) return;
  225.  
  226.                 for (rec=1; rec <= ihdr->idx_rec_cnt+1; rec++)
  227.                 {       idx = (INDEX_REC) rbuf;
  228.  
  229.                         if (idx->idx_idx_ptr == left)
  230.                                 break;
  231.  
  232.                         rbuf += fh->fh_rec_size;
  233.                 }
  234.  
  235.                 if (idx->idx_idx_ptr != left)
  236.                 {       db_error = DB_INVALID_INDEX;
  237.                         return;
  238.                 }
  239.         }
  240.  
  241.         idx->idx_idx_ptr = right;
  242.  
  243.         if (db_add_blk == tmp->buf_cur_blk)
  244.                 if (db_add_rec == cnt1 + 1)
  245.                 {       db_add_blk =  buf->buf_cur_blk;
  246.                         db_add_rec =  rec;
  247.                 }
  248.  
  249.         src = rbuf;
  250.         dst = rbuf + fh->fh_rec_size;
  251.         cnt = ((ihdr->idx_rec_cnt + 1) - rec + 1) * fh->fh_rec_size;
  252.         memcpy(dst, src, cnt);
  253.  
  254.         src = tmp->buf_data + sizeof(struct db_index_hdr)
  255.                                          + cnt1 * fh->f